Problem statement: zenit12kki
| I: Párty |
| 40 bodov | Časový limit: 1000 ms |
Po skončení súťažnej časti programu sa tanečníci tešia na veľkú párty s jahodami a šampanským.
Mnohí účastníci sú ale introvertní a hoci chuť majú, na párty sa hanbia ísť, ak sa
na nej nezúčastní určitý počet kamarátov.
Na prvom riadku vstupu sú tri celé čísla: počet súťažiacich N (1 ≤ N ≤ 200,000), počet dvojíc
kto sa s kým pozná M (0 ≤ M ≤ 600,000) a číslo K (0 ≤ K ≤ N−1). Súťažiacich
pre jednoduchosť označíme číslami 1 až N. Zámerne neprezradíme, ktoré číslo má Lukáš, aby
ste nemohli získať žiadnu informáciu o skutočnom počte jeho kamarátov.
Nasleduje M riadkov, na každom sú dve čísla popisujúce dvojicu účastníkov, ktorí sa kamarátia.
Môžete predpokladať, že tieto dve čísla sú z rozsahu 1 až N, sú rôzne a tiež že na každom
z týchto riadkov je rôzna dvojica čísel.
Každý z účastníkov je schopný ísť na párty len vtedy, ak sa na nej zúčastní aspoň K jeho kamarátov.
Podmnožina ľudí je vyhovujúca vtedy a len vtedy, ak pre každého
jej člena platí, že je v podmnožine aj K alebo viac jeho kamarátov.
Niektoré podmnožiny účastníkov túto podmienku spĺňajú a niektoré nespĺňajú. Napríklad prázdna množina
vyhovuje vždy. Nájdite najväčšiu vyhovujúcu množinu. Ak je takých viacero,
vypíšte ľubovoľnú z nich. Na prvom riadku výstupu je počet účastníkov párty.
Ak je tento počet kladný, tak výstup obsahuje aj druhý riadok.
Na ňom je zoznam účastníkov. Títo majú byť vypísaní v rastúcom poradí a
jednotlivé čísla majú byť oddelené práve jednou medzerou.
Táto úloha sa dá riešiť veľa rôznymi spôsobmi a získaný počet bodov bude spravodlivo
odvodený od časovej zložitosti vášho riešenia.
>
Príklady:
| |
9 8 2
1 7
1 5
2 8
2 5
4 9
6 4
2 7
2 1
|
| |
